package org.chnxi.datastructures.sort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertSorting {

    public static void main(String[] args) {
        //步骤拆解
        System.out.println("按步骤拆解：");
        int[] arr = {101, 34, 119, 1};
        insertSortByStep(arr);

        //直接实现
        System.out.println("直接实现：");
        int[] arr2 = {101, 34, 119, 1};
        insertSort(arr2);
        System.out.println("排序后："+Arrays.toString(arr2));

        System.out.println("测试大量数据的执行耗时：");
        int[] randomArr = new int[80000];
        for (int i =0; i<80000; i++){
            randomArr[i] = (int) (Math.random()*80000);
        }

        long start = System.currentTimeMillis();
        insertSort(randomArr);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));
    }

    public static void insertSortByStep(int[] arr){

        //第一轮
        //定义待插入的数
        int insertVal = arr[1];
        //arr[1]前面的下标
        int indertIdx = 1 - 1;

        // 1. indertIdx >= 0 保证数组不越界
        // 2. insertVal < arr[indertIdx] 还没找到插入位置
        // 3.
        while(indertIdx >= 0 && insertVal < arr[indertIdx]){
            arr[indertIdx + 1] = arr[indertIdx];
            indertIdx--;
        }
        //退出while循环时，插入位置找到，插入位置是insertIdx+1
        arr[indertIdx+1] = insertVal;

        System.out.println("第一轮后："+ Arrays.toString(arr));

        //第二轮
        //定义待插入的数
        insertVal = arr[2];
        //arr[1]前面的下标
        indertIdx = 2 - 1;

        // 1. indertIdx >= 0 保证数组不越界
        // 2. insertVal < arr[indertIdx] 还没找到插入位置
        // 3.
        while(indertIdx >= 0 && insertVal < arr[indertIdx]){
            arr[indertIdx + 1] = arr[indertIdx];
            indertIdx--;
        }
        //退出while循环时，插入位置找到，插入位置是insertIdx+1
        arr[indertIdx+1] = insertVal;

        System.out.println("第二轮后："+ Arrays.toString(arr));

        //第三轮
        //定义待插入的数
        insertVal = arr[3];
        //arr[1]前面的下标
        indertIdx = 3 - 1;

        // 1. indertIdx >= 0 保证数组不越界
        // 2. insertVal < arr[indertIdx] 还没找到插入位置
        // 3.
        while(indertIdx >= 0 && insertVal < arr[indertIdx]){
            arr[indertIdx + 1] = arr[indertIdx];
            indertIdx--;
        }
        //退出while循环时，插入位置找到，插入位置是insertIdx+1
        arr[indertIdx+1] = insertVal;

        System.out.println("第三轮后："+ Arrays.toString(arr));
    }

    public static void insertSort(int[] arr){
        int insertVal = 0;
        int insertIdx = 0;
        for (int i = 1; i < arr.length; i++){
            //定义待插入的数
            insertVal = arr[i];
            //arr[1]前面的下标
            insertIdx = i - 1;

            // 1. indertIdx >= 0 保证数组不越界
            // 2. insertVal < arr[indertIdx] 还没找到插入位置
            // 3. 需要将arr[insertIdx]后移
            while(insertIdx >= 0 && insertVal < arr[insertIdx]){
                arr[insertIdx + 1] = arr[insertIdx];
                insertIdx--;
            }
            //退出while循环时，插入位置找到，插入位置是insertIdx+1
            if(insertIdx + 1 != i){
                arr[insertIdx+1] = insertVal;
            }
        }
    }
}
